#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "mySort.h"

/* 冒泡排序 */
void bubbleSort(int *num, int size, enum way flag)
{
	int i, j, k, temp;

	for (i = 0; i < size - 1; i++)
	{
		for (j = 0; j < size - 1 -i; j++)
		{
			k = 0;
			if (flag == RISE)
			{
				if (num[j] > num[j+1])
				{
					k = 1;
				}
			}
			else if (flag == DECLINE)
			{
				if (num[j] < num[j+1])
				{
					k = 1;
				}
			}
			if (k)
			{
				temp = num[j];
				num[j] = num[j+1];
				num[j+1] = temp;
			}
		}
	}
}

/* 选择排序 */
void selectSort(int *num, int size, enum way flag)
{
	int i, j, k, temp;

	for (i = 0; i < size - 1; i++)
	{
		k = i;
		for (j = i + 1; j < size; j++)
		{
			if (flag == RISE)
			{
				if (num[k] > num[j])
				{
					k = j;
				}
			}
			else if (flag == DECLINE)
			{
				if (num[k] < num[j])
				{
					k = j;
				}
			}
		}
		if (k != i)
		{
			temp = num[k];	
			num[k] = num[i];
			num[i] = temp;
		}

	}
}

/* 插入排序 */
void insertSort(int *num, int size, enum way flag)
{
	int i, j;
	int min, max;

	for (i = 1; i < size; i++)
	{
		if (flag == RISE)
		{
			if (num[i-1] > num[i])
			{
				min = num[i];
				for (j = i - 1; j >= 0 && num[j] > min; j--)
				{
					num[j+1] = num[j];
				}
				num[j+1] = min;
			}
		}
		else if (flag == DECLINE)
		{
			if (num[i-1] < num[i])
			{
				max = num[i];
				for (j = i - 1; j >= 0 && num[j] < max; j--)
				{
					num[j+1] = num[j];
				}
				num[j+1] = max;
			}
		}
	}
}

/* 二分法插入排序 */
void dichotomySort(int *num, int size, int data)
{
	int min = 0;
	int max = size - 2;
	int mid;

	while (min < max)
	{
		mid = (min + max) / 2;
		if (data > num[mid])
		{
			min = mid + 1;
		}
		else
		{
			max = mid - 1;
		}
	}
	
	for (int i = size - 1; i != max + 1; i--)
	{
		num[i] = num[i-1];
	}
	num[max+1] = data;
}

/* 快速排序 */
void quickSort(int *num, int size, int L, int R)
{
	if (L >= R)
		return ;
	int left = L;
	int right = R;
	int pivot = num[left];

	while (left < right)
	{
		while (left < right && num[right] >= pivot)
		{
			right--;
		}
		if (left < right)
		{
			num[left] = num[right];
		}

		while (left < right && num[left] <= pivot)
		{
			left++;
		}
		if (left < right)
		{
			num[right] = num[left];
		}

		if (left >= right)
		{
			num[left] = pivot;
		}
	}
	quickSort(num, size, left + 1, R);
	quickSort(num, size, L, right - 1);
}

/* 希尔排序 */
void shellSort(int *num, int size)
{
	int i, j, min;
	int gap = size / 2;
	
	while (gap >= 1)
	{
		for (i = 0; i < size - gap; i++)
		{
			if (num[i] > num[i+gap])
			{
				min = num[i+gap];
				for (j = i; j >= 0 && num[j] > min; j -= gap)
					num[j+gap] = num[j];
				num[j+gap] = min;
			}
		}
		gap /= 2;
	}	
}

void mySort(int *num, int size, enum way flag, func sort)
{
	sort(num, size, flag);
}
